package com.algorithm.cjm.july.chapter1.ch2;

import java.util.Arrays;

/**
 * Created by jieming.chen on 2020/1/11
 */
public class StringContain3 {

    static StringContain3 object = new StringContain3();

    public static void main(String[] args) {
        String a = "bacdefg";
        String b = "w";
        boolean c = object.stringContain(a, b);
        System.out.println(c);

        String a1 = "bacdefg";
        String b1 = "b";
        boolean c1 = object.stringContain(a1, b1);
        System.out.println(c1);
    }

    /**
     * 素数相乘
     * 1. 遍历长字符串a,求得a 中的所有字母对应的素数的乘积
     * 2. 遍历短字符串b, 判断上一步得到的乘积能否被b 中的字母对应的素数整除
     * 3. 输出结果
     * O(m+n)
     *
     * @param a
     * @param b
     * @return
     */
    private boolean stringContain(String a, String b) {
        int[] p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        int f = 1;
        for (int i = 0; i < a.length(); i++) {
            int x = p[a.charAt(i) - 'a'];
            if (f % x != 0) {
                f *= x;
            }
        }
        for (int i = 0; i < b.length(); i++) {
            int x = p[b.charAt(i) - 'a'];
            if (f % x != 0) {
                return false;
            }
        }
        return true;
    }

}
